## Copyright (C) 2012 Estela Moura
## 
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
## 
## This program is distributed in the hope that it will be useful,
## but WITHOUT ANY WARRANTY; without even the implied warranty of
## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
## GNU General Public License for more details.
## 
## You should have received a copy of the GNU General Public License
## along with Octave; see the file COPYING.  If not, see
## <http://www.gnu.org/licenses/>.

## TSP_by_ACO(cidades, iteracoes)
## retorna: MelhorSolucao, SolucaoMedia

## Author: Estela Moura <estela@kubuntu-Inspiron>
## Created: 2012-06-13

function [MelhorSolucao, SolucaoMedia]=TSP_by_ACO(cidades, iteracoes);

  %%========================= Definição padrão de parâmetros ====================%
  %% peso do feromônio: alpha
  ExpFerom=1;
  %% peso do fator heurístico: beta
  ExpDist=5;
  %% fator de evaporação: rho
  FatEvap=0.5;
  %% parâmetro para incrementar o feromônio: Q
  Q=100;
  %% feromônio inicial: tau0
  FeromIni=1e-6;
  %% formigas elitistas: b
  FormiElit=5;
  %% Quantidade de formigas
  QuantFormi=size(cidades,1);
  %%=============================================================================%

  %% Obtendo matriz que contem as distâncias entre todos os pontos
  MatDistancia=matriz_distancia(cidades);

  %% Matriz de feromônio das arestas
  MatFerom=ones(size(cidades,1))*FeromIni;
  for(i=1:length(MatFerom))
    MatFerom(i,i)=0;
  endfor

  %% O número da linha é o ID da formiga.
  %% Colocando uma formiga em cada cidade.
  %% '+1' => retorna ao inicio
  Caminhos=zeros(QuantFormi, size(cidades,1)+1);
  Caminhos(:,1)=shuffle(cidades(:,1));

  %% Solução Default inicial
  MelhorSolucao.caminho=[(cidades(:,1)); 1];
  MelhorSolucao.comprimento=calcula_comprimento(size(cidades,1), MelhorSolucao.caminho, MatDistancia);

  %% Variável que guardará todos os comprimentos encontrados a cada iteração
  TodosComprimentos=zeros(1,QuantFormi);
  
  %% loop principal
  for(t=1:iteracoes)

    for(k=1:QuantFormi)	%Para todas as formigas formigas
      for(passo=1:size(cidades,1)-1)	%Vai percorrer todas as cidades
	CidadeAtual=Caminhos(k,passo);
	Visitadas=Caminhos(k,:);
	QuaisFaltam=setdiff(cidades(:,1), Visitadas);
	QuantasFaltam=length(QuaisFaltam);
	NumProb=zeros(1,QuantasFaltam);
	for(i=1:QuantasFaltam)
	  NumProb(i)=(MatFerom(CidadeAtual, QuaisFaltam(i)))^ExpFerom * (1/(MatDistancia(CidadeAtual, QuaisFaltam(i))))^ExpDist;
	endfor
	DenProb=sum(NumProb);
	Probabilidades=NumProb/DenProb;
	
	%escolhe uma cidade para ir
	colAtual=1;
	roleta=rand(1);
	while (roleta>=0)
		roleta=roleta-Probabilidades(colAtual);
		colAtual=colAtual+1;
	endwhile
	colAtual=colAtual-1; % necessário, pois a verificação de loop é feita APÓS incrementar.
	Caminhos(k, passo+1)=QuaisFaltam(colAtual); %cidade escolhida para ir.
	
      endfor
      
      %fecha o percurso
      Caminhos(k,size(cidades,1)+1)=Caminhos(k,1);
      
      %% Aplica 2OPT para todos os caminhos encontrados:
      Caminhos(k,:) = Heu2OPT (Caminhos(k,:), MatDistancia);
      
      %Encontrar o melhor caminho
      TodosComprimentos(k)=calcula_comprimento(size(cidades,1), Caminhos(k,:), MatDistancia);
      if(TodosComprimentos(k) < MelhorSolucao.comprimento)
				MelhorSolucao.comprimento=TodosComprimentos(k);
				MelhorSolucao.caminho=Caminhos(k,:);
				posmelhor = k;
      endif
    endfor
    
    %% Aplica o 2OPT só para o melhor caminho da iteração atual:
#       MelhorSolucao = Heu2OPT (MelhorSolucao, MatDistancia);
#       TodosComprimentos(posmelhor) = MelhorSolucao.comprimento;
    
    %============= Atualizando o feromônio ==================%
    %Fator de evaporação
    Evaporacao=MatFerom*(1-FatEvap);
    %Incrementar o feromônio dependendo de cada formiga.
    IncrementoPessoal=zeros(size(MatFerom));
    for(CadaFormiga=1:QuantFormi)
      for(coluna=1:size(Caminhos, 2)-1)
				i=Caminhos(CadaFormiga, coluna);
				j=Caminhos(CadaFormiga, coluna+1);
				IncrementoPessoal(i,j)=IncrementoPessoal(i,j)+(Q/TodosComprimentos(CadaFormiga));
      endfor
    endfor
    %Contribuição das formigas elitistas
    IncrementoElitista=zeros(size(MatFerom));
    for(coluna=1:size(MelhorSolucao.caminho)-1)
      i=MelhorSolucao.caminho(coluna);
      j=MelhorSolucao.caminho(coluna+1);
      IncrementoElitista(i,j)=IncrementoElitista(i,j)+(Q/MelhorSolucao.comprimento);
    endfor
    %De fato, o novo feromônio:
    MatFerom=Evaporacao+IncrementoPessoal+FormiElit*IncrementoElitista;
    
    %Atualizando nova partida das formigas
    Caminhos(:,1)=Caminhos(:,size(Caminhos, 2)-1);
    Caminhos(:,2:size(Caminhos, 2))=zeros(QuantFormi, size(cidades,1));
    TodosComprimentos=zeros(1,QuantFormi);
    
    VetMedia(1,t)=MelhorSolucao.comprimento;
    
  endfor

  SolucaoMedia=(sum(VetMedia))/(max(size(VetMedia)));
  
  %Visualizando o caminho encontrado.
  desenha_caminho(cidades, MelhorSolucao);

endfunction
